// 数据流的中位数
/*
 这题主要是要考虑addNum方法添加数据不是当前数组中的最大值时，要先找到对应位置再进行添加
 */
import Foundation

class MedianFinder {
    var nums = [Int]()
    /** initialize your data structure here. */
    init() {
        
    }
    
    func addNum(_ num: Int) {
        if nums.count == 0 || num > nums.last! {
            nums.append(num)
        }
        else {
            let index = findIndex(nums, num)
            nums.insert(num, at: index)
        }
    }
    
    func findMedian() -> Double {
        let mid = (nums.count - 1) / 2
        if nums.count % 2 == 0 {
            return Double(nums[mid] + nums[mid + 1]) / 2.0
        } else {
            return Double(nums[mid])
        }
    }
    
    func findIndex(_ array: [Int], _ num: Int) -> Int {
        var left = 0
        var right = array.count - 1
        while left < right {
            let mid = (left + right) / 2
            if array[mid] < num {
                left = mid + 1
            } else {
                right = mid
            }
        }
        return left
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * let obj = MedianFinder()
 * obj.addNum(num)
 * let ret_2: Double = obj.findMedian()
 */
